﻿
#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> IntVector;

typedef struct {
	int row;
	int col;
	IntVector vals;
} PointValues;

void copyArray(const int src[9][9], int dest[9][9]);
typedef struct SuDoKu {
	SuDoKu(int arr[9][9]) {
		copyArray(arr, this->arr);
	}
	int arr[9][9];
}SuDoKu;
typedef shared_ptr<SuDoKu> SuDoKuPtr;
typedef vector<SuDoKuPtr> SuDoKuPtrs;

typedef enum SudoKuType {
	TopLeft,
	TopRight,
	BottomLeft,
	BottomRight,
	Middle,
} SudoKuType;

SuDoKuPtr getSudoKu(const int arr[21][21], SudoKuType type);
void resolveSuDoKu(SuDoKuPtr p, SuDoKuPtrs &results);
IntVector doResolve(const int arr[9][9], int row, int col);
PointValues getLeastValuesPoint(const int arr[9][9]);
void print(const int arr[21][21]);
bool isValidResult(const int arr[9][9]);
bool getAndCheckNewMid(const SuDoKuPtr tl, const SuDoKuPtr tr, const SuDoKuPtr bl, const SuDoKuPtr br, SuDoKuPtr &mid);
void mergeResult(const SuDoKuPtr tl, const SuDoKuPtr tr, const SuDoKuPtr bl, const SuDoKuPtr br, const SuDoKuPtr mid, int arr[21][21]);

static int total = 0;

int main()
{
	int loop = 1;
	while (loop) {
		total = 0;
		int arr[21][21];
		cout << "请输入五联数独（21X21）：" << endl;
		for (int r = 0; r < 21; ++r) {
			for (int c = 0; c < 21; ++c) {
				cin >> arr[r][c];
			}
		}

		// 输出
		cout << "=================方案集==================" << endl;

		SuDoKuPtrs tl, tr, bl, br;
		resolveSuDoKu(getSudoKu(arr, TopLeft), tl);
		resolveSuDoKu(getSudoKu(arr, TopRight), tr);
		resolveSuDoKu(getSudoKu(arr, BottomLeft), bl);
		resolveSuDoKu(getSudoKu(arr, BottomRight), br);

		SuDoKuPtr mid = getSudoKu(arr, Middle);
		SuDoKuPtr null;
		SuDoKuPtrs::iterator tl_it, tr_it, bl_it, br_it;
		for (tl_it = tl.begin(); tl_it != tl.end(); ++tl_it) {
			SuDoKuPtr new_mid = SuDoKuPtr(new SuDoKu((mid->arr)));
			if (!getAndCheckNewMid(*tl_it, null, null, null, new_mid)) {
				continue;
			}
			for (tr_it = tr.begin(); tr_it != tr.end(); ++tr_it) {
				SuDoKuPtr new_mid = SuDoKuPtr(new SuDoKu((mid->arr)));
				if (!getAndCheckNewMid(*tl_it, *tr_it, null, null, new_mid)) {
					continue;
				}
				for (bl_it = bl.begin(); bl_it != bl.end(); ++bl_it) {
					SuDoKuPtr new_mid = SuDoKuPtr(new SuDoKu((mid->arr)));
					if (!getAndCheckNewMid(*tl_it, *tr_it, *bl_it, null, new_mid)) {
						continue;
					}
					for (br_it = br.begin(); br_it != br.end(); ++br_it) {
						SuDoKuPtr new_mid = SuDoKuPtr(new SuDoKu((mid->arr)));
						if (getAndCheckNewMid(*tl_it, *tr_it, *bl_it, *br_it, new_mid)) {
							SuDoKuPtrs mid_results;
							resolveSuDoKu(new_mid, mid_results);
							SuDoKuPtrs::iterator it;
							for (it = mid_results.begin(); it != mid_results.end(); ++it) {
								int rlt[21][21] = { 0 };
								mergeResult(*tl_it, *tr_it, *bl_it, *br_it, *it, rlt);
								print(rlt);
							}
						}
					}
				}
			}
		}

		cout << "继续请输入1，结束请输入0：";
		cin >> loop;
	}

}

SuDoKuPtr getSudoKu(const int arr[21][21], SudoKuType type) {
	int subArr[9][9];
	int i = 0, j = 0;
	switch (type)
	{
	case TopLeft:
		break;
	case TopRight:
		j = 12;
		break;
	case BottomLeft:
		i = 12;
		break;
	case BottomRight:
		i = 12;
		j = 12;
		break;
	case Middle:
		i = 6;
		j = 6;
		break;
	default:
		break;
	}

	for (int r = 0; r < 9 ; ++r) {
		for (int c = 0; c < 9; ++c) {
			subArr[r][c] = arr[r+i][c+j];
		}
	}

	return SuDoKuPtr(new SuDoKu(subArr));
}

void resolveSuDoKu(SuDoKuPtr p, SuDoKuPtrs &results) {
	bool resolved;
	do {
		resolved = false;
		for (int r = 0; r < 9; ++r) {
			for (int c = 0; c < 9; ++c) {
				if (p->arr[r][c] == 0) {
					IntVector vals = doResolve(p->arr, r, c);
					if (vals.size() == 1) {
						p->arr[r][c] = vals.front();
						resolved = true;
					}
					else if (vals.empty()) {
						// error
						return;
					}
				}
			}
		}
	} while (resolved);

	PointValues leastValuesPoint = getLeastValuesPoint(p->arr);
	if (leastValuesPoint.vals.empty()) {
		if (isValidResult(p->arr)) {
			results.push_back(p);
		}
	}
	else {
		IntVector::iterator it;
		for (it = leastValuesPoint.vals.begin(); it != leastValuesPoint.vals.end(); ++it) {
			SuDoKuPtr sp = SuDoKuPtr(new SuDoKu(p->arr));
			sp->arr[leastValuesPoint.row][leastValuesPoint.col] = *it;
			resolveSuDoKu(sp, results);
		}
	}
}

bool isValidResult(const int arr[9][9]) {
	for (int r = 0; r < 9; ++r) {
		for (int c = 0; c < 9; ++c) {
			if (arr[r][c] == 0) {
				return false;
			}
		}
	}
	return true;
}

IntVector doResolve(const int arr[9][9], int row, int col) {
	int vec[9] = { 0 };

	// scan row
	for (int i = 0; i < 9; ++i) {
		if (arr[row][i] > 0) {
			vec[arr[row][i] - 1]++;
		}
	}

	// scan col
	for (int i = 0; i < 9; ++i) {
		if (arr[i][col] > 0) {
			vec[arr[i][col] - 1]++;
		}
	}

	// scan grid
	int iStart = (row / 3) * 3;
	int jStart = (col / 3) * 3;
	for (int i = iStart; i < 3 + iStart; ++i) {
		for (int j = jStart; j < 3 + jStart; ++j) {
			if (i != row && j != col && arr[i][j] > 0) {
				vec[arr[i][j] - 1]++;
			}
		}
	}

	// count
	IntVector values;
	for (int i = 0; i < 9; ++i) {
		if (vec[i] == 0) {
			values.push_back(i + 1);
		}
	}

	return values;
}

PointValues getLeastValuesPoint(const int arr[9][9]) {
	PointValues leastValuesPoint;
	for (int r = 0; r < 9; ++r) {
		for (int c = 0; c < 9; ++c) {
			if (arr[r][c] == 0) {
				IntVector vals = doResolve(arr, r, c);
				if (leastValuesPoint.vals.empty() || leastValuesPoint.vals.size() > vals.size()) {
					leastValuesPoint.row = r;
					leastValuesPoint.col = c;
					leastValuesPoint.vals = vals;
				}
			}
		}
	}
	return leastValuesPoint;
}

void copyArray(const int src[9][9], int dest[9][9]) {
	for (int r = 0; r < 9; ++r) {
		for (int c = 0; c < 9; ++c) {
			dest[r][c] = src[r][c];
		}
	}
}

void print(const int arr[21][21]) {
	cout << "-----------------方案" << ++total << "-------------------" << endl;
	for (int r = 0; r < 21; ++r) {
		for (int c = 0; c < 21; ++c) {
			cout << arr[r][c] << " ";
		}
		cout << endl;
	}
}

bool getAndCheckNewMid(const SuDoKuPtr tl, const SuDoKuPtr tr, const SuDoKuPtr bl, const SuDoKuPtr br, SuDoKuPtr& mid) {
	// tl
	if (tl.get()) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				mid->arr[i][j] = tl->arr[i + 6][j + 6];
			}
		}
	}
	// tr
	if (tr.get()) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 6; j < 9; ++j) {
				mid->arr[i][j] = tr->arr[i + 6][j - 6];
			}
		}
	}
	// bl
	if (bl.get()) {
		for (int i = 6; i < 9; ++i) {
			for (int j = 0; j < 3; ++j) {
				mid->arr[i][j] = bl->arr[i - 6][j + 6];
			}
		}
	}
	// br
	if (br.get()) {
		for (int i = 6; i < 9; ++i) {
			for (int j = 6; j < 9; ++j) {
				mid->arr[i][j] = br->arr[i - 6][j - 6];
			}
		}
	}

	// check duplications
	int row[9] = { 0 };
	int col[9] = { 0 };
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			int iv = mid->arr[i][j];
			int jv = mid->arr[j][i];
			if (iv > 0) {
				iv--;
				row[iv]++;
			}
			if (jv > 0) {
				jv--;
				col[jv]++;
			}
			if (row[iv] > 1 || col[jv] > 1) {
				return false;
			}
		}

		// clear
		for (int k = 0; k < 9; ++k) {
			row[k] = 0;
			col[k] = 0;
		}
	}

	return true;
}

void mergeResult(const SuDoKuPtr tl, const SuDoKuPtr tr, const SuDoKuPtr bl, const SuDoKuPtr br, const SuDoKuPtr mid, int arr[21][21]) {
	// tl
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			arr[i][j] = tl->arr[i][j];
		}
	}
	// tr
	for (int i = 0; i < 9; ++i) {
		for (int j = 12; j < 21; ++j) {
			arr[i][j] = tr->arr[i][j - 12];
		}
	}
	// bl
	for (int i = 12; i < 21; ++i) {
		for (int j = 0; j < 9; ++j) {
			arr[i][j] = bl->arr[i - 12][j];
		}
	}
	// br
	for (int i = 12; i < 21; ++i) {
		for (int j = 12; j < 21; ++j) {
			arr[i][j] = br->arr[i - 12][j - 12];
		}
	}
	// mid
	for (int i = 6; i < 15; ++i) {
		for (int j = 6; j < 15; ++j) {
			arr[i][j] = mid->arr[i - 6][j - 6];
		}
	}
}
